package Week1.J0420;

// 1. 第一次误用了Queue 应该是先进后出
// 2. 忘记在只有一个Stack不为空时的进位情况
// 3. 忘记在最后一个Stack元素弹出后，仍有可能进位的情况 (e.g. 99+9)

import java.util.Stack;

public class 链表相加二 {


    public ListNode addInList (ListNode head1, ListNode head2) {

        Stack<ListNode> stack1 = new Stack<>();
        Stack<ListNode> stack2 = new Stack<>();

        while (head1 != null) {
            stack1.push(head1);
            head1 = head1.next;
        }
        while (head2 != null) {
            stack2.push(head2);
            head2 = head2.next;
        }

        ListNode head3 = new ListNode(0);
        int rem = 0;

        while (!stack1.isEmpty() || !stack2.isEmpty() || rem != 0) {
            int sum = rem;
            if (!stack1.isEmpty()) sum += stack1.pop().val;
            if (!stack2.isEmpty()) sum += stack2.pop().val;

            ListNode node = new ListNode(sum % 10);
            node.next = head3.next;
            head3.next = node;
        }

        // 因为head3头部为0，所以要返回head3.next
        return head3.next;
    }
}


class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}